1 Data

We load the real business dataset from a large e-commerce company, with 93 features for 10,000 products. We remove the \(id\) column from the dataset, since the index of each row uniquely identifies each product, too. Then, we scale the data in order have it correctly balanced.

# We load the data that will be used
PATH <- '~/Desktop/TERM 1/SMI/seminar4'
product_features <- read_csv(file.path(PATH,"product_features.csv"))
Rows: 10000 Columns: 94
── Column specification ───────────────────────────────────────────────────────────────────────────────────────────
Delimiter: ","
dbl (94): id, feat_1, feat_2, feat_3, feat_4, feat_5, feat_6, feat_7, feat_8, feat_9, feat_10, feat_11, feat_12...

ℹ Use `spec()` to retrieve the full column specification for this data.
ℹ Specify the column types or set `show_col_types = FALSE` to quiet this message.
ids <- product_features$id
product_features <- subset(product_features,select=-id)
product_features_scaled = scale(product_features)
product_features_scaled = as.data.frame(product_features_scaled)

2 Hard clustering

In order to know the optimal number of clusters to use, there are several methods to look for it. For all the upcoming methods we will try, we will set the maximum number of clusters to check equal to 10 for several reasons.First, because we want to decrease computational time it will take. Then, so we can check different methods and algorithms without having to work with a subset of the data. Lastly, because it may not make sense to group the samples in many different groups, therefore limiting the maximum number of clusters to 10.

2.1 Gap statistics

First, we will first run a gap statistics and check for the resulting optimal value. This method compares the total within intra-cluster variation for different values of \(k\), with their expected values under null reference distribution of the data. The estimate of the optimal clusters will be the value of \(k\) that maximizes the gap statistic (that is, the one yielding the largest gap statistic). Therefore, the clustering structure is far away from the random uniform distribution of points.

Now, we will run the gap statistics using different algorithms for the kmeans and hence, see if the results have similarities or not. The three algorithms we will use are: Hartigan and Wong (by default), MacQueen and Lloyd. On one hand, the MacQueen algorithm works similar to Hartigan and Wong: it updates the centroids any time a point is moved and also, makes clever time-saving choices in checking for the closest cluster. On the other hand, the Lloyd algorithm is the first and simplest of all these clustering algorithms: firstly, randomly partitions the data into \(k\) sets; then, computes the centroid of each set and assigns each point to the closest centroid and finally, repeats these steps until nothing changes or the maximum number of iterations is reached.

Let’s compute all algorithms and display our results:

p1 <- fviz_gap_stat(gap_stat) + ggtitle("Hartigan and Wong")
p2 <- fviz_gap_stat(gap_stat_mcq) + ggtitle("MacQueen")
p3 <- fviz_gap_stat(gap_stat_llo) + ggtitle("Lloyd")

grid.arrange(p1, p2, p3, nrow = 2)

We can see that the optimal number of clusters returned by the gap statistics function for Hartigan and Wong, MacQueen and Lloyd algorithm are, respectively, 7, 8 and 10. However, for Hartigan and Wong, the gap statistics increases after that, having another pick at \(k=10\) and therefore, closer to the other solutions provided by MacQueen and Lloyd. Hence, we could conclude that, as per the gap statistics, the optimal number of clusters would have a value of \(k=9\) (computing the mean of the three values).

2.2 Elbow method

We can also use the Elbow Method in order to try and find the optimal number of clusters, in which the sum of squares at each number of clusters is calculated and graphed. We are searching for a change of slope, from steep to shallow (just like an elbow looks) to determine the optimal number of clusters. This method is inexact, but still potentially helpful, so we will compute it, again trying the three algorithms we explained before, and obtain the following result:

# function to compute total within-cluster sum of square 
sum_of_squares <- function(k) {
  kmeans(product_features_scaled, k, nstart = 10)$tot.withinss
}
sum_of_squares_mcq <- function(k) {
  kmeans(product_features_scaled, k, nstart = 10, algorithm='MacQueen')$tot.withinss
}
sum_of_squares_llo <- function(k) {
  kmeans(product_features_scaled, k, nstart = 10, algorithm='Lloyd')$tot.withinss
}

# Compute and plot sum_of_squares for k = 1 to k = 10
k.values <- 1:10

# extract sum_of_squares for 2-10 clusters
sum_of_squares_values <- map_dbl(k.values, sum_of_squares)
sum_of_squares_df <- data.frame(k=k.values, sum_of_squares= sum_of_squares_values)

sum_of_squares_mcq_values <- map_dbl(k.values, sum_of_squares_mcq)
sum_of_squares__mcq_df <- data.frame(k=k.values, sum_of_squares_mcq= sum_of_squares_mcq_values)

sum_of_squares_llo_values <- map_dbl(k.values, sum_of_squares_llo)
sum_of_squares_llo_df <- data.frame(k=k.values, sum_of_squares_llo= sum_of_squares_llo_values)
em1 <- ggplot(sum_of_squares_df, aes(x=k,y=sum_of_squares)) + 
  geom_point() +
  geom_line() +
  xlab("Number of clusters K") +
  ylab("Sum of squares") + 
  ggtitle("Hartigan and Wong")

em2 <- ggplot(sum_of_squares__mcq_df, aes(x=k,y=sum_of_squares_mcq)) + 
  geom_point() +
  geom_line() +
  xlab("Number of clusters K") +
  ylab("Sum of squares") + 
  ggtitle("MacQueen")

em3 <- ggplot(sum_of_squares_llo_df, aes(x=k,y=sum_of_squares_llo)) + 
  geom_point() +
  geom_line() +
  xlab("Number of clusters K") +
  ylab("Sum of squares") + 
  ggtitle("Lloyd")

grid.arrange(em1, em2, em3, nrow = 2)

As we said, this method is not an exact procedure to determine the optimal number of clusters and as we can see, there is not a clear change of slope anywhere in the graph. There may be two light slope changes, one around \(k=3\) and another one around \(k=9\), but non of them are totally conclusive. Hence, we will keep the obtained result with the gap statistics for the optimal number of clusters.

2.3 Clustering trees

Finally, we will now use a different \(R\) package, which doesn’t explicitly tell you the correct choice of optimal clusters, but it can be useful for exploring possible choices and also, it gives us a nice graphical explanation of how information goes from one cluster to another whenever there is a change in \(k\).

The clustree \(R\) package takes an alternative approach: it considers how samples change groupings as the number of clusters increases. Therefore, it is useful for showing which clusters are distinct and which are unstable. We will now display the result and explain what it actually means. In order to save computational time, we will only compute it with one clustering algorithm: since, as we said before, both MacQueen or Hartigan and Wong work in a more efficient way than LLoyd, we will choose one of them. So, since Hartigan and Wong had a peak in the optimal \(k=9\) value we have finally chosen, we will use this algorithm.

# We plot the tree with the obtained results:
# a visualisation for interrogating clusterings as resolution increases.
clustree(df, prefix='k')

Firstly, point out that the legend of the figure is being cut off. Hence, we will add here the information missing from the legend. In this figure, the size of each node corresponds to the number of samples in each cluster (from 2000 to 8000 for each size), and the arrows are coloured according to the number of samples each cluster receives, as it can be seen in the legend. A separate set of arrows, the transparent ones, are called the incoming node proportion and they show how samples from one group end up in another group; that is, an indicator of cluster instability. The more transparent the arrow is, the lower the proportion of samples that change is. Furthermore, when a node has multiple incoming edges, the clustering tree is indicating that we over-clustered the data.

Again, this method does not provide the optimal number of clusters, it just nicely displays how samples move as the clustering resolution increases and thus, it is a nice way to explore the data.

2.4 Plotting with optimal \(k\)

After having used several methods to try and understand the clustering it can be done with our data, we choose an optimal number of clusters of value \(k=9\). Therefore, we will now compute the corresponding kmeans algorithm and plot the results. Again, as we did for the clustering trees, we will use the Hartigan and Wong algorithm.

Since a 2D-plot can be confusing and difficult to visually understand, we will use a 3D-plot instead. With the package \(plotly\), we will display a 3D-graph where the axis will correspond to the 3 most important features, obtained through a PCA done in our data.

Here, we display the following obtained results:

pc <- princomp(product_features_scaled, cor=TRUE, scores = TRUE)
optimal_kmeans <- kmeans(product_features_scaled, centers = 9, nstart = 25)
product_features_scaled$cluster <- as.factor(optimal_kmeans$cluster)
axx <- list(
  title = "x; 1st PC"
)
axy <- list(
  title = "y; 2nd PC"
)
axz <- list(
  title = "z; 3rd PC"
)
x_ax=~pc$scores[,1]
y_ax=~pc$scores[,2]
z_ax=~pc$scores[,3]
plot_3d <- plot_ly(product_features_scaled,x=x_ax, y=y_ax, z=z_ax,color=~cluster) %>%
     add_markers(size=1.5)
plot_3d <- plot_3d %>% layout(scene = list(xaxis=axx,yaxis=axy,zaxis=axz))
#layout(title = '3D-plot for k=9', xaxis=list(title='1st PC'))
plot_3d

3 Soft clustering

We load again the data, since we added the clusters column to our original data, to work with the correct data structure.

product_features_soft_clust <- read_csv(file.path(PATH,"product_features.csv"))
Rows: 10000 Columns: 94
── Column specification ───────────────────────────────────────────────────────────────────────────────────────────
Delimiter: ","
dbl (94): id, feat_1, feat_2, feat_3, feat_4, feat_5, feat_6, feat_7, feat_8, feat_9, feat_10, feat_11, feat_12...

ℹ Use `spec()` to retrieve the full column specification for this data.
ℹ Specify the column types or set `show_col_types = FALSE` to quiet this message.
product_features_soft_clust <- subset(product_features_soft_clust,select=-id)
product_features_soft_clust_scaled = scale(product_features_soft_clust)
product_features_soft_clust_scaled = as.data.frame(product_features_soft_clust_scaled)
pc2 <- princomp(product_features_soft_clust_scaled, cor=TRUE, scores = TRUE)

Now, we will now obtain an EM Gaussian Mixture Model (GMM) with the \(Mclust\) built-in function of \(R\). This function fits a GMM by an EM algorithm for different values of the number of clusters and different constraints on the covariance matrices of the Gaussian components. Then, the function chooses the best model, in which we have the type of GMM and the number of components, using the BIC criterion. Now, instead of choosing the optimal number of clusters (as we did in hard clustering), we want to choose the number of mixture components.

Following, we compute the function and show the obtained results:

plot(soft_clust, what = "BIC", ylim = range(soft_clust$BIC[,-(1:2)], na.rm = TRUE),
     legendArgs = list(x = "bottomleft"))

summary(soft_clust)
---------------------------------------------------- 
Gaussian finite mixture model fitted by EM algorithm 
---------------------------------------------------- 

Mclust VEV (ellipsoidal, equal shape) model with 8 components: 

Clustering table:
   1    2    3    4    5    6    7    8 
1434 1612  890 1450 1209  754 1187 1464 

We can see that the model returns an optimal number of mixture components equals to 8, which is very similar to the optimal number of clusters obtained with hard clustering (\(k=9\)). Therefore, using this result, we run the soft clustering function with this unique value passed to G and finally, we again 3D plot the results, with the 3 axis being the first three principal components of the data, too.


x_ax2=~pc2$scores[,1]
y_ax2=~pc2$scores[,2]
z_ax2=~pc2$scores[,3]

plot_3d_soft <- plot_ly(product_features_soft_clust_scaled,x=x_ax2, y=y_ax2,  
                        z=z_ax2, color=as.character(soft_clust_optimal$classification)) %>%
     add_markers(size=1.5)
plot_3d_soft <- plot_3d_soft %>% layout(scene = list(xaxis=axx,yaxis=axy,zaxis=axz))
#layout(title = '3D-plot for k=9', xaxis=list(title='1st PC'))
plot_3d_soft
LS0tCnRpdGxlOiAiU3RhdGlzdGljYWwgTW9kZWxsaW5nIGFuZCBJbmZlcmVuY2UgLSBTZW1pbmFyIDQiCmF1dGhvcjogIlNlcmdpby1ZZXJzaSBWaWxsZWdhcyBQZWxlZ3LDrW4iCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgY29kZV9mb2xkaW5nOiBoaWRlCiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiAzCiAgICBudW1iZXJfc2VjdGlvbnM6IHllcwotLS0KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRSwgaW5jbHVkZT1GQUxTRSwgcmVzdWx0cz0naGlkZSd9CiMgV2UgZmlyc3QgbG9hZCB0aGUgcmVxdWlyZWQgbGlicmFyaWVzIGluIG9yZGVyIHRvIGJlIGFibGUgdG8gcnVuIHRoZSBjb2RlOgpsaWJyYXJ5KGdncmFwaCkgIyBHcmFwaGljYWwgcGFja2FnZQpsaWJyYXJ5KHRpZHl2ZXJzZSkgICMgRGF0YSBtYW5pcHVsYXRpb24KbGlicmFyeShjbHVzdGVyKSAjQ2x1c3RlcmluZwpsaWJyYXJ5KGZhY3RvZXh0cmEpICMgQ2x1c3RlcmluZyBhbGdvcml0aG1zICYgdmlzdWFsaXphdGlvbgpsaWJyYXJ5KGdyaWRFeHRyYSkgIyBNdWx0aXBsZSBwbG90dGluZyB3aXRoIGdncGxvdDIKbGlicmFyeShtY2x1c3QpICMgTWNsdXN0IHNvZnQgY2x1c3RlcmluZwpsaWJyYXJ5KHBsb3RseSkgIyAzRCBwbG90CmxpYnJhcnkoZHBseXIpICMgQmFzaWMgUiBwYWNrYWdlCmxpYnJhcnkoY2x1c3RyZWUpICMgQ2x1c3RlcmluZyB0cmVlcwpgYGAKIyBEYXRhCldlIGxvYWQgdGhlIHJlYWwgYnVzaW5lc3MgZGF0YXNldCBmcm9tIGEgbGFyZ2UgZS1jb21tZXJjZSBjb21wYW55LCB3aXRoIDkzIGZlYXR1cmVzIGZvciAxMCwwMDAgcHJvZHVjdHMuIFdlIHJlbW92ZSB0aGUgJGlkJCBjb2x1bW4gZnJvbSB0aGUgZGF0YXNldCwgc2luY2UgdGhlIGluZGV4IG9mIGVhY2ggcm93IHVuaXF1ZWx5IGlkZW50aWZpZXMgZWFjaCBwcm9kdWN0LCB0b28uIFRoZW4sIHdlIHNjYWxlIHRoZSBkYXRhIGluIG9yZGVyIGhhdmUgaXQgY29ycmVjdGx5IGJhbGFuY2VkLgpgYGB7cn0KIyBXZSBsb2FkIHRoZSBkYXRhIHRoYXQgd2lsbCBiZSB1c2VkClBBVEggPC0gJ34vRGVza3RvcC9URVJNIDEvU01JL3NlbWluYXI0Jwpwcm9kdWN0X2ZlYXR1cmVzIDwtIHJlYWRfY3N2KGZpbGUucGF0aChQQVRILCJwcm9kdWN0X2ZlYXR1cmVzLmNzdiIpKQppZHMgPC0gcHJvZHVjdF9mZWF0dXJlcyRpZApwcm9kdWN0X2ZlYXR1cmVzIDwtIHN1YnNldChwcm9kdWN0X2ZlYXR1cmVzLHNlbGVjdD0taWQpCnByb2R1Y3RfZmVhdHVyZXNfc2NhbGVkID0gc2NhbGUocHJvZHVjdF9mZWF0dXJlcykKcHJvZHVjdF9mZWF0dXJlc19zY2FsZWQgPSBhcy5kYXRhLmZyYW1lKHByb2R1Y3RfZmVhdHVyZXNfc2NhbGVkKQpgYGAKIyBIYXJkIGNsdXN0ZXJpbmcKCkluIG9yZGVyIHRvIGtub3cgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzIHRvIHVzZSwgdGhlcmUgYXJlIHNldmVyYWwgbWV0aG9kcyB0byBsb29rIGZvciBpdC4gRm9yIGFsbCB0aGUgdXBjb21pbmcgbWV0aG9kcyB3ZSB3aWxsIHRyeSwgd2Ugd2lsbCBzZXQgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNsdXN0ZXJzIHRvIGNoZWNrIGVxdWFsIHRvIDEwIGZvciBzZXZlcmFsIHJlYXNvbnMuRmlyc3QsIGJlY2F1c2Ugd2Ugd2FudCB0byBkZWNyZWFzZSBjb21wdXRhdGlvbmFsIHRpbWUgaXQgd2lsbCB0YWtlLiBUaGVuLCBzbyB3ZSBjYW4gY2hlY2sgZGlmZmVyZW50IG1ldGhvZHMgYW5kIGFsZ29yaXRobXMgd2l0aG91dCBoYXZpbmcgdG8gd29yayB3aXRoIGEgc3Vic2V0IG9mIHRoZSBkYXRhLiBMYXN0bHksIGJlY2F1c2UgaXQgbWF5IG5vdCBtYWtlIHNlbnNlIHRvIGdyb3VwIHRoZSBzYW1wbGVzIGluIG1hbnkgZGlmZmVyZW50IGdyb3VwcywgdGhlcmVmb3JlIGxpbWl0aW5nIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjbHVzdGVycyB0byAxMC4KCiMjIEdhcCBzdGF0aXN0aWNzCkZpcnN0LCB3ZSB3aWxsIGZpcnN0IHJ1biBhIGdhcCBzdGF0aXN0aWNzIGFuZCBjaGVjayBmb3IgdGhlIHJlc3VsdGluZyBvcHRpbWFsIHZhbHVlLiBUaGlzIG1ldGhvZCBjb21wYXJlcyB0aGUgdG90YWwgd2l0aGluIGludHJhLWNsdXN0ZXIgdmFyaWF0aW9uIGZvciBkaWZmZXJlbnQgdmFsdWVzIG9mICRrJCwgd2l0aCB0aGVpciBleHBlY3RlZCB2YWx1ZXMgdW5kZXIgbnVsbCByZWZlcmVuY2UgZGlzdHJpYnV0aW9uIG9mIHRoZSBkYXRhLiBUaGUgZXN0aW1hdGUgb2YgdGhlIG9wdGltYWwgY2x1c3RlcnMgd2lsbCBiZSB0aGUgdmFsdWUgb2YgJGskIHRoYXQgbWF4aW1pemVzIHRoZSBnYXAgc3RhdGlzdGljICh0aGF0IGlzLCB0aGUgb25lIHlpZWxkaW5nIHRoZSBsYXJnZXN0IGdhcCBzdGF0aXN0aWMpLiBUaGVyZWZvcmUsIHRoZSBjbHVzdGVyaW5nIHN0cnVjdHVyZSBpcyBmYXIgYXdheSBmcm9tIHRoZSByYW5kb20gdW5pZm9ybSBkaXN0cmlidXRpb24gb2YgcG9pbnRzLiAKCk5vdywgd2Ugd2lsbCBydW4gdGhlIGdhcCBzdGF0aXN0aWNzIHVzaW5nIGRpZmZlcmVudCBhbGdvcml0aG1zIGZvciB0aGUga21lYW5zIGFuZCBoZW5jZSwgc2VlIGlmIHRoZSByZXN1bHRzIGhhdmUgc2ltaWxhcml0aWVzIG9yIG5vdC4gVGhlIHRocmVlIGFsZ29yaXRobXMgd2Ugd2lsbCB1c2UgYXJlOiBIYXJ0aWdhbiBhbmQgV29uZyAoYnkgZGVmYXVsdCksIE1hY1F1ZWVuIGFuZCBMbG95ZC4gT24gb25lIGhhbmQsIHRoZSBNYWNRdWVlbiBhbGdvcml0aG0gd29ya3Mgc2ltaWxhciB0byBIYXJ0aWdhbiBhbmQgV29uZzogaXQgdXBkYXRlcyB0aGUgY2VudHJvaWRzIGFueSB0aW1lIGEgcG9pbnQgaXMgbW92ZWQgYW5kIGFsc28sIG1ha2VzIGNsZXZlciB0aW1lLXNhdmluZyBjaG9pY2VzIGluIGNoZWNraW5nIGZvciB0aGUgY2xvc2VzdCBjbHVzdGVyLiBPbiB0aGUgb3RoZXIgaGFuZCwgdGhlIExsb3lkIGFsZ29yaXRobSBpcyB0aGUgZmlyc3QgYW5kIHNpbXBsZXN0IG9mIGFsbCB0aGVzZSBjbHVzdGVyaW5nIGFsZ29yaXRobXM6IGZpcnN0bHksIHJhbmRvbWx5IHBhcnRpdGlvbnMgdGhlIGRhdGEgaW50byAkayQgc2V0czsgdGhlbiwgY29tcHV0ZXMgdGhlIGNlbnRyb2lkIG9mIGVhY2ggc2V0IGFuZCBhc3NpZ25zIGVhY2ggcG9pbnQgdG8gdGhlIGNsb3Nlc3QgY2VudHJvaWQgYW5kIGZpbmFsbHksIHJlcGVhdHMgdGhlc2Ugc3RlcHMgdW50aWwgbm90aGluZyBjaGFuZ2VzIG9yIHRoZSBtYXhpbXVtIG51bWJlciBvZiBpdGVyYXRpb25zIGlzIHJlYWNoZWQuCgpMZXQncyBjb21wdXRlIGFsbCBhbGdvcml0aG1zIGFuZCBkaXNwbGF5IG91ciByZXN1bHRzOgpgYGB7ciwgZWNobz1GQUxTRSwgcmVzdWx0cz0naGlkZScsIHdhcm5pbmc9RkFMU0UsbWVzc2FnZT1GQUxTRX0KZ2FwX3N0YXQgPC0gY2x1c0dhcChwcm9kdWN0X2ZlYXR1cmVzX3NjYWxlZCwgRlVOID0ga21lYW5zLCBuc3RhcnQgPSAyNSwKICAgICAgICAgICAgICAgICAgICBpdGVyLm1heD0yMCwgSy5tYXggPSAxMCwgQiA9IDE1KSAKZ2FwX3N0YXRfbWNxIDwtIGNsdXNHYXAocHJvZHVjdF9mZWF0dXJlc19zY2FsZWQsIEZVTiA9IGttZWFucywgbnN0YXJ0ID0gMjUsCiAgICAgICAgICAgICAgICAgICAgYWxnb3JpdGhtPSdNYWNRdWVlbicsaXRlci5tYXg9MjAsIEsubWF4ID0gMTAsIEIgPSAxNSkgCmdhcF9zdGF0X2xsbyA8LSBjbHVzR2FwKHByb2R1Y3RfZmVhdHVyZXNfc2NhbGVkLCBGVU4gPSBrbWVhbnMsIG5zdGFydCA9IDI1LAogICAgICAgICAgICAgICAgICAgIGFsZ29yaXRobT0nTGxveWQnLGl0ZXIubWF4PTIwLCBLLm1heCA9IDEwLCBCID0gMTUpIApgYGAKCmBgYHtyfQpwMSA8LSBmdml6X2dhcF9zdGF0KGdhcF9zdGF0KSArIGdndGl0bGUoIkhhcnRpZ2FuIGFuZCBXb25nIikKcDIgPC0gZnZpel9nYXBfc3RhdChnYXBfc3RhdF9tY3EpICsgZ2d0aXRsZSgiTWFjUXVlZW4iKQpwMyA8LSBmdml6X2dhcF9zdGF0KGdhcF9zdGF0X2xsbykgKyBnZ3RpdGxlKCJMbG95ZCIpCgpncmlkLmFycmFuZ2UocDEsIHAyLCBwMywgbnJvdyA9IDIpCmBgYAoKV2UgY2FuIHNlZSB0aGF0IHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycyByZXR1cm5lZCBieSB0aGUgZ2FwIHN0YXRpc3RpY3MgZnVuY3Rpb24gZm9yIEhhcnRpZ2FuIGFuZCBXb25nLCBNYWNRdWVlbiBhbmQgTGxveWQgYWxnb3JpdGhtIGFyZSwgcmVzcGVjdGl2ZWx5LCA3LCA4IGFuZCAxMC4gSG93ZXZlciwgZm9yIEhhcnRpZ2FuIGFuZCBXb25nLCB0aGUgZ2FwIHN0YXRpc3RpY3MgaW5jcmVhc2VzIGFmdGVyIHRoYXQsIGhhdmluZyBhbm90aGVyIHBpY2sgYXQgJGs9MTAkIGFuZCB0aGVyZWZvcmUsIGNsb3NlciB0byB0aGUgb3RoZXIgc29sdXRpb25zIHByb3ZpZGVkIGJ5IE1hY1F1ZWVuIGFuZCBMbG95ZC4gSGVuY2UsIHdlIGNvdWxkIGNvbmNsdWRlIHRoYXQsIGFzIHBlciB0aGUgZ2FwIHN0YXRpc3RpY3MsIHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycyB3b3VsZCBoYXZlIGEgdmFsdWUgb2YgJGs9OSQgKGNvbXB1dGluZyB0aGUgbWVhbiBvZiB0aGUgdGhyZWUgdmFsdWVzKS4gCgojIyBFbGJvdyBtZXRob2QKV2UgY2FuIGFsc28gdXNlIHRoZSBFbGJvdyBNZXRob2QgaW4gb3JkZXIgdG8gdHJ5IGFuZCBmaW5kIHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycywgaW4gd2hpY2ggdGhlIHN1bSBvZiBzcXVhcmVzIGF0IGVhY2ggbnVtYmVyIG9mIGNsdXN0ZXJzIGlzIGNhbGN1bGF0ZWQgYW5kIGdyYXBoZWQuIFdlIGFyZSBzZWFyY2hpbmcgZm9yIGEgY2hhbmdlIG9mIHNsb3BlLCBmcm9tIHN0ZWVwIHRvIHNoYWxsb3cgKGp1c3QgbGlrZSBhbiBlbGJvdyBsb29rcykgdG8gZGV0ZXJtaW5lIHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycy4gVGhpcyBtZXRob2QgaXMgaW5leGFjdCwgYnV0IHN0aWxsIHBvdGVudGlhbGx5IGhlbHBmdWwsIHNvIHdlIHdpbGwgY29tcHV0ZSBpdCwgYWdhaW4gdHJ5aW5nIHRoZSB0aHJlZSBhbGdvcml0aG1zIHdlIGV4cGxhaW5lZCBiZWZvcmUsIGFuZCBvYnRhaW4gdGhlIGZvbGxvd2luZyByZXN1bHQ6CgpgYGB7ciwgd2FybmluZz1GQUxTRX0KIyBmdW5jdGlvbiB0byBjb21wdXRlIHRvdGFsIHdpdGhpbi1jbHVzdGVyIHN1bSBvZiBzcXVhcmUgCnN1bV9vZl9zcXVhcmVzIDwtIGZ1bmN0aW9uKGspIHsKICBrbWVhbnMocHJvZHVjdF9mZWF0dXJlc19zY2FsZWQsIGssIG5zdGFydCA9IDEwKSR0b3Qud2l0aGluc3MKfQpzdW1fb2Zfc3F1YXJlc19tY3EgPC0gZnVuY3Rpb24oaykgewogIGttZWFucyhwcm9kdWN0X2ZlYXR1cmVzX3NjYWxlZCwgaywgbnN0YXJ0ID0gMTAsIGFsZ29yaXRobT0nTWFjUXVlZW4nKSR0b3Qud2l0aGluc3MKfQpzdW1fb2Zfc3F1YXJlc19sbG8gPC0gZnVuY3Rpb24oaykgewogIGttZWFucyhwcm9kdWN0X2ZlYXR1cmVzX3NjYWxlZCwgaywgbnN0YXJ0ID0gMTAsIGFsZ29yaXRobT0nTGxveWQnKSR0b3Qud2l0aGluc3MKfQoKIyBDb21wdXRlIGFuZCBwbG90IHN1bV9vZl9zcXVhcmVzIGZvciBrID0gMSB0byBrID0gMTAKay52YWx1ZXMgPC0gMToxMAoKIyBleHRyYWN0IHN1bV9vZl9zcXVhcmVzIGZvciAyLTEwIGNsdXN0ZXJzCnN1bV9vZl9zcXVhcmVzX3ZhbHVlcyA8LSBtYXBfZGJsKGsudmFsdWVzLCBzdW1fb2Zfc3F1YXJlcykKc3VtX29mX3NxdWFyZXNfZGYgPC0gZGF0YS5mcmFtZShrPWsudmFsdWVzLCBzdW1fb2Zfc3F1YXJlcz0gc3VtX29mX3NxdWFyZXNfdmFsdWVzKQoKc3VtX29mX3NxdWFyZXNfbWNxX3ZhbHVlcyA8LSBtYXBfZGJsKGsudmFsdWVzLCBzdW1fb2Zfc3F1YXJlc19tY3EpCnN1bV9vZl9zcXVhcmVzX19tY3FfZGYgPC0gZGF0YS5mcmFtZShrPWsudmFsdWVzLCBzdW1fb2Zfc3F1YXJlc19tY3E9IHN1bV9vZl9zcXVhcmVzX21jcV92YWx1ZXMpCgpzdW1fb2Zfc3F1YXJlc19sbG9fdmFsdWVzIDwtIG1hcF9kYmwoay52YWx1ZXMsIHN1bV9vZl9zcXVhcmVzX2xsbykKc3VtX29mX3NxdWFyZXNfbGxvX2RmIDwtIGRhdGEuZnJhbWUoaz1rLnZhbHVlcywgc3VtX29mX3NxdWFyZXNfbGxvPSBzdW1fb2Zfc3F1YXJlc19sbG9fdmFsdWVzKQpgYGAKCmBgYHtyfQplbTEgPC0gZ2dwbG90KHN1bV9vZl9zcXVhcmVzX2RmLCBhZXMoeD1rLHk9c3VtX29mX3NxdWFyZXMpKSArIAogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9saW5lKCkgKwogIHhsYWIoIk51bWJlciBvZiBjbHVzdGVycyBLIikgKwogIHlsYWIoIlN1bSBvZiBzcXVhcmVzIikgKyAKICBnZ3RpdGxlKCJIYXJ0aWdhbiBhbmQgV29uZyIpCgplbTIgPC0gZ2dwbG90KHN1bV9vZl9zcXVhcmVzX19tY3FfZGYsIGFlcyh4PWsseT1zdW1fb2Zfc3F1YXJlc19tY3EpKSArIAogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9saW5lKCkgKwogIHhsYWIoIk51bWJlciBvZiBjbHVzdGVycyBLIikgKwogIHlsYWIoIlN1bSBvZiBzcXVhcmVzIikgKyAKICBnZ3RpdGxlKCJNYWNRdWVlbiIpCgplbTMgPC0gZ2dwbG90KHN1bV9vZl9zcXVhcmVzX2xsb19kZiwgYWVzKHg9ayx5PXN1bV9vZl9zcXVhcmVzX2xsbykpICsgCiAgZ2VvbV9wb2ludCgpICsKICBnZW9tX2xpbmUoKSArCiAgeGxhYigiTnVtYmVyIG9mIGNsdXN0ZXJzIEsiKSArCiAgeWxhYigiU3VtIG9mIHNxdWFyZXMiKSArIAogIGdndGl0bGUoIkxsb3lkIikKCmdyaWQuYXJyYW5nZShlbTEsIGVtMiwgZW0zLCBucm93ID0gMikKYGBgCgpBcyB3ZSBzYWlkLCB0aGlzIG1ldGhvZCBpcyBub3QgYW4gZXhhY3QgcHJvY2VkdXJlIHRvIGRldGVybWluZSB0aGUgb3B0aW1hbCBudW1iZXIgb2YgY2x1c3RlcnMgYW5kIGFzIHdlIGNhbiBzZWUsIHRoZXJlIGlzIG5vdCBhIGNsZWFyIGNoYW5nZSBvZiBzbG9wZSBhbnl3aGVyZSBpbiB0aGUgZ3JhcGguIFRoZXJlIG1heSBiZSB0d28gbGlnaHQgc2xvcGUgY2hhbmdlcywgb25lIGFyb3VuZCAkaz0zJCBhbmQgYW5vdGhlciBvbmUgYXJvdW5kICRrPTkkLCBidXQgbm9uIG9mIHRoZW0gYXJlIHRvdGFsbHkgY29uY2x1c2l2ZS4gSGVuY2UsIHdlIHdpbGwga2VlcCB0aGUgb2J0YWluZWQgcmVzdWx0IHdpdGggdGhlIGdhcCBzdGF0aXN0aWNzIGZvciB0aGUgb3B0aW1hbCBudW1iZXIgb2YgY2x1c3RlcnMuCgojIyBDbHVzdGVyaW5nIHRyZWVzCkZpbmFsbHksIHdlIHdpbGwgbm93IHVzZSBhIGRpZmZlcmVudCAkUiQgcGFja2FnZSwgd2hpY2ggZG9lc27igJl0IGV4cGxpY2l0bHkgdGVsbCB5b3UgdGhlIGNvcnJlY3QgY2hvaWNlIG9mIG9wdGltYWwgY2x1c3RlcnMsIGJ1dCBpdCBjYW4gYmUgdXNlZnVsIGZvciBleHBsb3JpbmcgcG9zc2libGUgY2hvaWNlcyBhbmQgYWxzbywgaXQgZ2l2ZXMgdXMgYSBuaWNlIGdyYXBoaWNhbCBleHBsYW5hdGlvbiBvZiBob3cgaW5mb3JtYXRpb24gZ29lcyBmcm9tIG9uZSBjbHVzdGVyIHRvIGFub3RoZXIgd2hlbmV2ZXIgdGhlcmUgaXMgYSBjaGFuZ2UgaW4gJGskLiAKClRoZSBjbHVzdHJlZSAkUiQgcGFja2FnZSB0YWtlcyBhbiBhbHRlcm5hdGl2ZSBhcHByb2FjaDogaXQgY29uc2lkZXJzIGhvdyBzYW1wbGVzIGNoYW5nZSBncm91cGluZ3MgYXMgdGhlIG51bWJlciBvZiBjbHVzdGVycyBpbmNyZWFzZXMuIFRoZXJlZm9yZSwgaXQgaXMgdXNlZnVsIGZvciBzaG93aW5nIHdoaWNoIGNsdXN0ZXJzIGFyZSBkaXN0aW5jdCBhbmQgd2hpY2ggYXJlIHVuc3RhYmxlLiBXZSB3aWxsIG5vdyBkaXNwbGF5IHRoZSByZXN1bHQgYW5kIGV4cGxhaW4gd2hhdCBpdCBhY3R1YWxseSBtZWFucy4gSW4gb3JkZXIgdG8gc2F2ZSBjb21wdXRhdGlvbmFsIHRpbWUsIHdlIHdpbGwgb25seSBjb21wdXRlIGl0IHdpdGggb25lIGNsdXN0ZXJpbmcgYWxnb3JpdGhtOiBzaW5jZSwgYXMgd2Ugc2FpZCBiZWZvcmUsIGJvdGggTWFjUXVlZW4gb3IgSGFydGlnYW4gYW5kIFdvbmcgd29yayBpbiBhIG1vcmUgZWZmaWNpZW50IHdheSB0aGFuIExMb3lkLCB3ZSB3aWxsIGNob29zZSBvbmUgb2YgdGhlbS4gU28sIHNpbmNlIEhhcnRpZ2FuIGFuZCBXb25nIGhhZCBhIHBlYWsgaW4gdGhlIG9wdGltYWwgJGs9OSQgdmFsdWUgd2UgaGF2ZSBmaW5hbGx5IGNob3Nlbiwgd2Ugd2lsbCB1c2UgdGhpcyBhbGdvcml0aG0uCgpgYGB7ciwgZWNobz1GQUxTRSwgcmVzdWx0cz0naGlkZScsIHdhcm5pbmc9RkFMU0UsbWVzc2FnZT1GQUxTRX0KIyBEZWZpbmUgYSBudWxsIHZlY3RvciB3aGljaCB3aWxsIGJlIGl0ZXJhdGl2ZWx5IHVwZGF0ZWQKY190cmVlIDwtIE5VTEwKCiMgVXBkYXRlIHRoZSBudWxsIHZlY3RvciB3aXRoIHRoZSByZXN1bHRzIGZvciBlYWNoIGttZWFucywKIyB3aGVyZSB3ZSB3aWxsIHRyeSB1bnRpbCBrPTExCmZvciAoayBpbiAxOjEwKXsKICBjX3RyZWVba10gPC0ga21lYW5zKHByb2R1Y3RfZmVhdHVyZXNfc2NhbGVkLCBrLCBuc3RhcnQgPSAzMCkKfQoKIyBHZXQgYSBkYXRhZnJhbWUgd2l0aCB0aGUgaW5mb3JtYXRpb24gY29udGFpbmVkIG9mIGFsbCBrbWVhbnMKZGYgPC0gZGF0YS5mcmFtZShjX3RyZWUpCgojIEFkZCBhbiBzcGVjaWZpYyBuYW1lIGZvciBlYWNoIGNvbHVtbgpjb2xuYW1lcyhkZikgPC0gc2VxKDE6MTApCmNvbG5hbWVzKGRmKSA8LSBwYXN0ZTAoImsiLGNvbG5hbWVzKGRmKSkKCiMgQ29tcHV0ZXMgYSBQcmluY2lwYWwgQ29tcG9uZW50IEFuYWx5c2lzIChQQ0EpCiMgYW5kIHN0b3JlcyB0aGUgcmVzdWx0LCB1cGRhdGluZyB0aGUgZGF0YWZyYW1lCmRmLnBjYSA8LSBwcmNvbXAoZGYsIGNlbnRlciA9IFRSVUUsIHNjYWxlLiA9IEZBTFNFKQppbmQuY29vcmQgPC0gZGYucGNhJHgKaW5kLmNvb3JkIDwtIGluZC5jb29yZFssMToyXQpkZiA8LSBiaW5kX2NvbHMoYXMuZGF0YS5mcmFtZShkZiksIGFzLmRhdGEuZnJhbWUoaW5kLmNvb3JkKSkKYGBgCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQojIFdlIHBsb3QgdGhlIHRyZWUgd2l0aCB0aGUgb2J0YWluZWQgcmVzdWx0czoKIyBhIHZpc3VhbGlzYXRpb24gZm9yIGludGVycm9nYXRpbmcgY2x1c3RlcmluZ3MgYXMgcmVzb2x1dGlvbiBpbmNyZWFzZXMuCmNsdXN0cmVlKGRmLCBwcmVmaXg9J2snKQpgYGAKRmlyc3RseSwgcG9pbnQgb3V0IHRoYXQgdGhlIGxlZ2VuZCBvZiB0aGUgZmlndXJlIGlzIGJlaW5nIGN1dCBvZmYuIEhlbmNlLCB3ZSB3aWxsIGFkZCBoZXJlIHRoZSBpbmZvcm1hdGlvbiBtaXNzaW5nIGZyb20gdGhlIGxlZ2VuZC4gSW4gdGhpcyBmaWd1cmUsIHRoZSBzaXplIG9mIGVhY2ggbm9kZSBjb3JyZXNwb25kcyB0byB0aGUgbnVtYmVyIG9mIHNhbXBsZXMgaW4gZWFjaCBjbHVzdGVyIChmcm9tIDIwMDAgdG8gODAwMCBmb3IgZWFjaCBzaXplKSwgYW5kIHRoZSBhcnJvd3MgYXJlIGNvbG91cmVkIGFjY29yZGluZyB0byB0aGUgbnVtYmVyIG9mIHNhbXBsZXMgZWFjaCBjbHVzdGVyIHJlY2VpdmVzLCBhcyBpdCBjYW4gYmUgc2VlbiBpbiB0aGUgbGVnZW5kLiBBIHNlcGFyYXRlIHNldCBvZiBhcnJvd3MsIHRoZSB0cmFuc3BhcmVudCBvbmVzLCBhcmUgY2FsbGVkIHRoZSBpbmNvbWluZyBub2RlIHByb3BvcnRpb24gYW5kIHRoZXkgc2hvdyBob3cgc2FtcGxlcyBmcm9tIG9uZSBncm91cCBlbmQgdXAgaW4gYW5vdGhlciBncm91cDsgdGhhdCBpcywgYW4gaW5kaWNhdG9yIG9mIGNsdXN0ZXIgaW5zdGFiaWxpdHkuIFRoZSBtb3JlIHRyYW5zcGFyZW50IHRoZSBhcnJvdyBpcywgdGhlIGxvd2VyIHRoZSBwcm9wb3J0aW9uIG9mIHNhbXBsZXMgdGhhdCBjaGFuZ2UgaXMuIEZ1cnRoZXJtb3JlLCB3aGVuIGEgbm9kZSBoYXMgbXVsdGlwbGUgaW5jb21pbmcgZWRnZXMsIHRoZSBjbHVzdGVyaW5nIHRyZWUgaXMgaW5kaWNhdGluZyB0aGF0IHdlIG92ZXItY2x1c3RlcmVkIHRoZSBkYXRhLgoKQWdhaW4sIHRoaXMgbWV0aG9kIGRvZXMgbm90IHByb3ZpZGUgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzLCBpdCBqdXN0IG5pY2VseSBkaXNwbGF5cyBob3cgc2FtcGxlcyBtb3ZlIGFzIHRoZSBjbHVzdGVyaW5nIHJlc29sdXRpb24gaW5jcmVhc2VzIGFuZCB0aHVzLCBpdCBpcyBhIG5pY2Ugd2F5IHRvIGV4cGxvcmUgdGhlIGRhdGEuCgojIyBQbG90dGluZyB3aXRoIG9wdGltYWwgJGskCgpBZnRlciBoYXZpbmcgdXNlZCBzZXZlcmFsIG1ldGhvZHMgdG8gdHJ5IGFuZCB1bmRlcnN0YW5kIHRoZSBjbHVzdGVyaW5nIGl0IGNhbiBiZSBkb25lIHdpdGggb3VyIGRhdGEsIHdlIGNob29zZSBhbiBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycyBvZiB2YWx1ZSAkaz05JC4gVGhlcmVmb3JlLCB3ZSB3aWxsIG5vdyBjb21wdXRlIHRoZSBjb3JyZXNwb25kaW5nIGttZWFucyBhbGdvcml0aG0gYW5kIHBsb3QgdGhlIHJlc3VsdHMuIEFnYWluLCBhcyB3ZSBkaWQgZm9yIHRoZSBjbHVzdGVyaW5nIHRyZWVzLCB3ZSB3aWxsIHVzZSB0aGUgSGFydGlnYW4gYW5kIFdvbmcgYWxnb3JpdGhtLgoKU2luY2UgYSAyRC1wbG90IGNhbiBiZSBjb25mdXNpbmcgYW5kIGRpZmZpY3VsdCB0byB2aXN1YWxseSB1bmRlcnN0YW5kLCB3ZSB3aWxsIHVzZSBhIDNELXBsb3QgaW5zdGVhZC4gV2l0aCB0aGUgcGFja2FnZSAkcGxvdGx5JCwgd2Ugd2lsbCBkaXNwbGF5IGEgM0QtZ3JhcGggd2hlcmUgdGhlIGF4aXMgd2lsbCBjb3JyZXNwb25kIHRvIHRoZSAzIG1vc3QgaW1wb3J0YW50IGZlYXR1cmVzLCBvYnRhaW5lZCB0aHJvdWdoIGEgUENBIGRvbmUgaW4gb3VyIGRhdGEuIAoKSGVyZSwgd2UgZGlzcGxheSB0aGUgZm9sbG93aW5nIG9idGFpbmVkIHJlc3VsdHM6CgpgYGB7ciwgd2FybmluZz1GQUxTRX0KcGMgPC0gcHJpbmNvbXAocHJvZHVjdF9mZWF0dXJlc19zY2FsZWQsIGNvcj1UUlVFLCBzY29yZXMgPSBUUlVFKQpvcHRpbWFsX2ttZWFucyA8LSBrbWVhbnMocHJvZHVjdF9mZWF0dXJlc19zY2FsZWQsIGNlbnRlcnMgPSA5LCBuc3RhcnQgPSAyNSkKcHJvZHVjdF9mZWF0dXJlc19zY2FsZWQkY2x1c3RlciA8LSBhcy5mYWN0b3Iob3B0aW1hbF9rbWVhbnMkY2x1c3RlcikKYGBgCgpgYGB7ciwgd2FybmluZz1GQUxTRX0KYXh4IDwtIGxpc3QoCiAgdGl0bGUgPSAieDsgMXN0IFBDIgopCmF4eSA8LSBsaXN0KAogIHRpdGxlID0gInk7IDJuZCBQQyIKKQpheHogPC0gbGlzdCgKICB0aXRsZSA9ICJ6OyAzcmQgUEMiCikKeF9heD1+cGMkc2NvcmVzWywxXQp5X2F4PX5wYyRzY29yZXNbLDJdCnpfYXg9fnBjJHNjb3Jlc1ssM10KcGxvdF8zZCA8LSBwbG90X2x5KHByb2R1Y3RfZmVhdHVyZXNfc2NhbGVkLHg9eF9heCwgeT15X2F4LCB6PXpfYXgsY29sb3I9fmNsdXN0ZXIpICU+JQogICAgIGFkZF9tYXJrZXJzKHNpemU9MS41KQpwbG90XzNkIDwtIHBsb3RfM2QgJT4lIGxheW91dChzY2VuZSA9IGxpc3QoeGF4aXM9YXh4LHlheGlzPWF4eSx6YXhpcz1heHopKQojbGF5b3V0KHRpdGxlID0gJzNELXBsb3QgZm9yIGs9OScsIHhheGlzPWxpc3QodGl0bGU9JzFzdCBQQycpKQpwbG90XzNkCmBgYAoKIyBTb2Z0IGNsdXN0ZXJpbmcKCldlIGxvYWQgYWdhaW4gdGhlIGRhdGEsIHNpbmNlIHdlIGFkZGVkIHRoZSBjbHVzdGVycyBjb2x1bW4gdG8gb3VyIG9yaWdpbmFsIGRhdGEsIHRvIHdvcmsgd2l0aCB0aGUgY29ycmVjdCBkYXRhIHN0cnVjdHVyZS4KYGBge3J9CnByb2R1Y3RfZmVhdHVyZXNfc29mdF9jbHVzdCA8LSByZWFkX2NzdihmaWxlLnBhdGgoUEFUSCwicHJvZHVjdF9mZWF0dXJlcy5jc3YiKSkKcHJvZHVjdF9mZWF0dXJlc19zb2Z0X2NsdXN0IDwtIHN1YnNldChwcm9kdWN0X2ZlYXR1cmVzX3NvZnRfY2x1c3Qsc2VsZWN0PS1pZCkKcHJvZHVjdF9mZWF0dXJlc19zb2Z0X2NsdXN0X3NjYWxlZCA9IHNjYWxlKHByb2R1Y3RfZmVhdHVyZXNfc29mdF9jbHVzdCkKcHJvZHVjdF9mZWF0dXJlc19zb2Z0X2NsdXN0X3NjYWxlZCA9IGFzLmRhdGEuZnJhbWUocHJvZHVjdF9mZWF0dXJlc19zb2Z0X2NsdXN0X3NjYWxlZCkKcGMyIDwtIHByaW5jb21wKHByb2R1Y3RfZmVhdHVyZXNfc29mdF9jbHVzdF9zY2FsZWQsIGNvcj1UUlVFLCBzY29yZXMgPSBUUlVFKQpgYGAKCk5vdywgd2Ugd2lsbCBub3cgb2J0YWluIGFuIEVNIEdhdXNzaWFuIE1peHR1cmUgTW9kZWwgKEdNTSkgd2l0aCB0aGUgJE1jbHVzdCQgYnVpbHQtaW4gZnVuY3Rpb24gb2YgJFIkLiBUaGlzIGZ1bmN0aW9uIGZpdHMgYSBHTU0gYnkgYW4gRU0gYWxnb3JpdGhtIGZvciBkaWZmZXJlbnQgdmFsdWVzIG9mIHRoZSBudW1iZXIgb2YgY2x1c3RlcnMgYW5kIGRpZmZlcmVudCBjb25zdHJhaW50cyBvbiB0aGUgY292YXJpYW5jZSBtYXRyaWNlcyBvZiB0aGUgR2F1c3NpYW4gY29tcG9uZW50cy4gVGhlbiwgdGhlIGZ1bmN0aW9uIGNob29zZXMgdGhlIGJlc3QgbW9kZWwsIGluIHdoaWNoIHdlIGhhdmUgdGhlIHR5cGUgb2YgR01NIGFuZCB0aGUgbnVtYmVyIG9mIGNvbXBvbmVudHMsIHVzaW5nIHRoZSBCSUMgY3JpdGVyaW9uLiBOb3csIGluc3RlYWQgb2YgY2hvb3NpbmcgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzIChhcyB3ZSBkaWQgaW4gaGFyZCBjbHVzdGVyaW5nKSwgd2Ugd2FudCB0byBjaG9vc2UgdGhlIG51bWJlciBvZiBtaXh0dXJlIGNvbXBvbmVudHMuCgpGb2xsb3dpbmcsIHdlIGNvbXB1dGUgdGhlIGZ1bmN0aW9uIGFuZCBzaG93IHRoZSBvYnRhaW5lZCByZXN1bHRzOgpgYGB7ciwgZWNobz1GQUxTRSwgcmVzdWx0cz0naGlkZScsIHdhcm5pbmc9RkFMU0UsbWVzc2FnZT1GQUxTRX0Kc29mdF9jbHVzdCA8LSBNY2x1c3QocHJvZHVjdF9mZWF0dXJlc19zb2Z0X2NsdXN0X3NjYWxlZCwgRz0xOjEwKQpgYGAKCmBgYHtyfQpwbG90KHNvZnRfY2x1c3QsIHdoYXQgPSAiQklDIiwgeWxpbSA9IHJhbmdlKHNvZnRfY2x1c3QkQklDWywtKDE6MildLCBuYS5ybSA9IFRSVUUpLAogICAgIGxlZ2VuZEFyZ3MgPSBsaXN0KHggPSAiYm90dG9tbGVmdCIpKQpgYGAKCmBgYHtyfQpzdW1tYXJ5KHNvZnRfY2x1c3QpCmBgYApXZSBjYW4gc2VlIHRoYXQgdGhlIG1vZGVsIHJldHVybnMgYW4gb3B0aW1hbCBudW1iZXIgb2YgbWl4dHVyZSBjb21wb25lbnRzIGVxdWFscyB0byA4LCB3aGljaCBpcyB2ZXJ5IHNpbWlsYXIgdG8gdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzIG9idGFpbmVkIHdpdGggaGFyZCBjbHVzdGVyaW5nICgkaz05JCkuIFRoZXJlZm9yZSwgdXNpbmcgdGhpcyByZXN1bHQsIHdlIHJ1biB0aGUgc29mdCBjbHVzdGVyaW5nIGZ1bmN0aW9uIHdpdGggdGhpcyB1bmlxdWUgdmFsdWUgcGFzc2VkIHRvIEcgYW5kIGZpbmFsbHksIHdlIGFnYWluIDNEIHBsb3QgdGhlIHJlc3VsdHMsIHdpdGggdGhlIDMgYXhpcyBiZWluZyB0aGUgZmlyc3QgdGhyZWUgcHJpbmNpcGFsIGNvbXBvbmVudHMgb2YgdGhlIGRhdGEsIHRvby4KYGBge3IsIGVjaG89RkFMU0UsIHJlc3VsdHM9J2hpZGUnLCB3YXJuaW5nPUZBTFNFLG1lc3NhZ2U9RkFMU0V9CnNvZnRfY2x1c3Rfb3B0aW1hbCA8LSBNY2x1c3QocHJvZHVjdF9mZWF0dXJlc19zb2Z0X2NsdXN0X3NjYWxlZCwgRz1jKDgpLCBtb2RlbE5hbWVzID0gYygnVkVWJykpCmBgYAoKYGBge3IsIHdhcm5pbmc9RkFMU0V9Cgp4X2F4Mj1+cGMyJHNjb3Jlc1ssMV0KeV9heDI9fnBjMiRzY29yZXNbLDJdCnpfYXgyPX5wYzIkc2NvcmVzWywzXQoKcGxvdF8zZF9zb2Z0IDwtIHBsb3RfbHkocHJvZHVjdF9mZWF0dXJlc19zb2Z0X2NsdXN0X3NjYWxlZCx4PXhfYXgyLCB5PXlfYXgyLCAgCiAgICAgICAgICAgICAgICAgICAgICAgIHo9el9heDIsIGNvbG9yPWFzLmNoYXJhY3Rlcihzb2Z0X2NsdXN0X29wdGltYWwkY2xhc3NpZmljYXRpb24pKSAlPiUKICAgICBhZGRfbWFya2VycyhzaXplPTEuNSkKcGxvdF8zZF9zb2Z0IDwtIHBsb3RfM2Rfc29mdCAlPiUgbGF5b3V0KHNjZW5lID0gbGlzdCh4YXhpcz1heHgseWF4aXM9YXh5LHpheGlzPWF4eikpCiNsYXlvdXQodGl0bGUgPSAnM0QtcGxvdCBmb3Igaz05JywgeGF4aXM9bGlzdCh0aXRsZT0nMXN0IFBDJykpCnBsb3RfM2Rfc29mdApgYGAKCgo=